package org.usmile.algorithms.learn.graph.direction;

import org.usmile.algorithms.learn.graph.Graph;

import java.util.LinkedList;
import java.util.List;

public class TopologySortDFS {

    public List<Integer> sort(DirectionAdjSet graph) {
        boolean[] visited = new boolean[graph.getV()];
        boolean[] inOnPath = new boolean[graph.getV()];
        LinkedList<Integer> result = new LinkedList<>();
        for (int v = 0; v < graph.getV(); v++) {
            if (!visited[v]) {
                if (dfs(graph, v, inOnPath, visited, result)) {
                    break;
                }
            }
        }

        return result;
    }

    private boolean dfs(Graph graph, int v, boolean[] isOnPath, boolean[] visited, LinkedList<Integer> result) {
        visited[v] = true;
        isOnPath[v] = true;
        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                if (dfs(graph, w, isOnPath, visited, result)) {
                    return true;
                }
            } else {
                if (isOnPath[w]) {
                    return true;
                }
            }
        }
        isOnPath[v] = false;
        result.addFirst(v);

        return false;
    }

    public static void main(String[] args) {
        DirectionAdjSet graph = new DirectionAdjSet(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
//        graph.addEdge(3, 0);
        graph.addEdge(3, 2);
        graph.addEdge(2, 4);
//        graph.addEdge(4, 3);

        System.out.println(new TopologySortDFS().sort(graph));
    }
}
